package OptimalAlgorithm.DivideAndConquer_Merge;
//https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/
import java.util.ArrayList;
import java.util.List;

public class CountSmaller {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int[] ret = new int[nums.length];
        int[] index = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            index[i] = i;
        }
        mergeSort(nums,0,nums.length - 1,ret,index);
        for (int i = 0; i < nums.length; i++) {
            list.add(ret[i]);
        }
        return list;
    }
    private void mergeSort(int[] nums,int left,int right,int[] ret,int[] index){
        if(left >= right){
            return;
        }
        int mid = (right + left) / 2;
        mergeSort(nums,left,mid,ret,index);
        mergeSort(nums,mid + 1,right,ret,index);
        merge(nums,left,mid,right,ret,index);//合并两个有序数组
    }
    //找一左一右找数字，策略2：固定左边(s1)数字，在右边(s2)找有多少比它小（数字降序）
    private void merge(int[] nums,int left,int mid,int right,int[] ret,int[] index){
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int tempIndex = 0;
        int[] temp = new int[right - left + 1];
        int tmpIndex = 0;
        int[] tmp = new int[right - left + 1];
        while (s1 <= e1 && s2 <= e2){
            if(nums[s1] <= nums[s2]){
                temp[tempIndex++] = nums[s2];//进行归并
                tmp[tmpIndex++] = index[s2++];//对归并的下标同步修改
            }else {
                ret[index[s1]] += e2 - s2 + 1;//对应原下标：index[s1]
                tmp[tmpIndex++] = index[s1];
                temp[tempIndex++] = nums[s1++];
            }
        }
        while (s1 <= e1){
            tmp[tmpIndex++] = index[s1];
            temp[tempIndex++] = nums[s1++];
        }
        while (s2 <= e2){
            tmp[tmpIndex++] = index[s2];
            temp[tempIndex++] = nums[s2++];
        }
        for (int i = left; i <= right; i++) {
            nums[i] = temp[i - left];
            index[i] =tmp[i - left];
        }
    }
}
